package 我的Java学习_算法基础.day_04;

public class _064_最大子方阵优化 {
    public static void main(String[] args) {
        int[][] a = {
                {1,1,1,1},
                {1,0,1,1},
                {1,1,1,1},
                {1,0,0,1}
        };
        int n = find(a);
        print(rec,a.length);
        System.out.println("==================================");
        System.out.println(n);
    }
    static int[][][] rec;   //辅助表

    private static int find(int[][] a){ //找寻边界为1最大子方阵
        int n =a.length;
        generateHelpRec(a);
        while(n>0){
            for(int i =0;i<a.length;i++){
                for(int j =0;j<a.length;j++){
                    if(check(i,j,n)){
                        return n;
                    }
                }
            }
            n--;
        }
        return 0;
    }

    private static void generateHelpRec(int[][] a){
        int n = a.length;
        rec = new int[n][n][2];
        int row = n-1;
        //初始化最后一行
        for(int j = n- 1;j>=0;j--){
            int value = a[row][j];
            if(value==1){
                if(j==n-1){
                    rec[row][j][0]=1;   //右侧连续1的个数
                }else{
                    rec[row][j][0] = rec[row][j+1][0]+1;
                }
                rec[row][j][1]=1;   //下方连续的数
            }

        }
        row--;
        for(int i =row;i>=0;i--){
            for(int j = n-1;j>=0;j--){
                int value = a[i][j];
                if(value==1){
                    if(j==n-1){
                        rec[i][j][0]=1;
                    }else{
                        rec[i][j][0]=rec[i][j+1][0]+1;
                    }
                    rec[i][j][1]=rec[i+1][j][1]+1;
                }

            }
        }

    }
    private static boolean check(int i,int j,int n){
        //左上角向右数有多于n个1
        //左上角向下数有多于n个1
        //左下角向右数有多于n个1
        //右上角向下数有多于n个1
        if(rec[i][j][0]>=n&&rec[i][j][1]>=n&&rec[i+n-1][j][0]>=n&&rec[i][j+n-1][1]>=n){
            return true;
        }else{
            return false;
        }
    }
    static void print(int[][][] a,int n){
        for(int i =0;i<n;i++){
            for(int j =0 ;j<n;j++){
                System.out.print(a[i][j][0]+","+a[i][j][1]+"\t");
            }
            System.out.println();
        }
    }
}
